import { btPrint } from "hy-algokit";

export class TreeNode<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent?: TreeNode<T> | null = null;

  value: T;
  constructor(value: T) {
    this.value = value;
  }

  //是否是左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this);
  }

  //是否是右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this);
  }
}

export class AVLTreeNode<T> extends TreeNode<T> {
  left: AVLTreeNode<T> | null = null;
  right: AVLTreeNode<T> | null = null;
  parent: AVLTreeNode<T> | null = null;

  height: number = 1;

  //获得树的高度，最长的子节点level
  private getHeight(): number {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    return Math.max(leftHeight, rightHeight) + 1;
  }

  //平衡因子左侧高度减去右侧高度
  private getBalanceFactor() {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    return leftHeight - rightHeight;
  }

  //直接判断当前节点是否平衡 平衡因子在【-1，1】区域为正常，其他为不平衡
  public get isBalanced(): boolean {
    return this.getBalanceFactor() >= -1 && this.getBalanceFactor() <= 1;
  }

  //获取更高子节点
  public get higherChild(): AVLTreeNode<T> | null {
    const leftHeight = this.left ? this.left.getHeight() : 0;
    const rightHeight = this.right ? this.right.getHeight() : 0;

    if (leftHeight > rightHeight) return this.left;
    if (leftHeight < rightHeight) return this.right;

    return this.isLeft ? this.left : this.right;
  }

  //右旋转
  rightRotation() {
    //判断节点是父节点的左节点还是右节点，提前判断，后续root已经被改不好判断
    const isLeft = this.isLeft;
    const isRight = this.right;

    //1.找到轴心节点
    const pivot = this.left!;
    pivot.parent = this.parent;

    //2.处理轴心节点的右节点，将其移动到root节点的左侧
    this.left = pivot.right;
    if (pivot.right) {
      pivot.right.parent = this;
    }

    //3.处理根节点
    pivot.right = this;
    this.parent = pivot;
    //4.挂在旋转后的轴心节点
    if (!pivot.parent) {
      //根节点
      //pivot直接作为tree的根
      return pivot;
    } else if (isLeft) {
      //pivot作为父节点的左子节点
      pivot.parent.left = pivot;
    } else if (isRight) {
      //pivot作为父节点的右子节点
      pivot.parent.right = pivot;
    }
    return pivot;
  }
}

//mock
// const avl = new AVLTreeNode<number>(10);
// avl.left = new AVLTreeNode<number>(8);
// avl.left.parent = avl;
// avl.left.left = new AVLTreeNode<number>(5);
// avl.left.left.parent = avl.left.left;

// const parent = new AVLTreeNode(12);
// parent.left = avl;

// avl.parent = parent;
// btPrint(parent);

// avl.rightRotation();

// btPrint(parent);
